The PPP protocol is a link layer protocol developed to provide an auto configuring, multi-protocol mechanism for exchanging variable length packets over serial point-to-point links. One protocol that can be transported over PPP is the IP.
When both real-time critical traffic and low priority traffic are sent in the same IP network over PPP links, it is very important that the real-time critical traffic is not interfered by the low priority traffic in order to fulfil the delay requirements of the real-time critical traffic. This is of course dependent on the link technology that is being used. However, the present invention concerns preferably PPP links. Even if the delay requirements of the real-time critical traffic are important to fulfil, the lower priority traffic may also have delay requirements. Therefore, this lower priority traffic must also be considered.
If the low priority IP packets are long, the transmission of such packets may block the link for a long period of time. (The length of an IP packet may differ from e.g. 40 bytes to 1500 bytes.) This is solved by fragmentation of the IP packets at PPP level by using the PPP Multilink Protocol (MP), which is further described in K. Sklower et. al., “The PPP Multilink Protocol (MP)”, RFC 1990. Originally, the MP was a protocol that facilitated the use of several physical links as one logic link. One part of the standard also defines a method for splitting and recombining packets.
The fragmentation creates shorter packets, which decreases the blocking time for the real-time critical traffic (high priority traffic). The use of MP introduces extra queues at the link layer besides the original PPP queue. More than one queue at the link layer for a certain router introduces a need for a scheduler at the link layer as showed in FIG. 7a. 
Each MP fragment comprises a PPP header, an MP header and a payload portion. There are two versions of the MP header; a long header and a short header. The long header has a size of four bytes and the short header has a size of two bytes. Which of the two headers that is used depends on the maximum number of MP fragments that is needed (2^10 or 2^24) for a fragmentation of one IP packet, since the difference between the two headers is the number of bits that indicates a sequence number. The sequence number indicates the order of the MP fragments of an IP packet. If a B-bit (Beginning) is marked in an MP fragment, it indicates that this is the beginning of the IP packet and if an E-bit (End) is marked, that indicates accordingly that the fragment is the end of the IP packet. The header keeps track on in what order the fragments should be reassembled by using a sequence number, which also results in that no re-ordering occurs between the reassembled IP packets. FIG. 1 shows the Multilink PPP (MP) header formats. The long header is shown in 102 and the short header is shown in 104. It should be noted that some bits in FIG. 1 are used for MP Multi-Class Extension which is further described below. (When Multi-Class Extension (MCE) is not used, the MCE bits are spare bits.)
When using MP for fragmentation, the fragmentation is performed per PPP link and the fragments must be reassembled to an IP packet at the end of every link as shown in FIG. 7c. FIG. 7c shows a number of routers 720 connected via PPP links 722, that may be one physical link or a bundle of PPP links, where each IP packet 724 is fragmented (1) into MP MCE fragments 726 and defragmented (2) into IP packets at each router 720. If MP fragmentation is performed for several hops in a row, the IP packets are fragmented and reassembled (i.e. defragmented) at every hop provided that fragmentation is used. Since the fragments have lower priority than real-time critical packets (e.g. voice), they are probably not sent “back-to-back”, (back-to-back means that the fragments are sent immediately after each other). It is more time consuming to send an MP fragmented IP packet than an unfragmented IP packet due to the extra overhead, but the major part of the extra delay is due to the waiting time introduced when other fragments/frames (of higher priority) are sent between the MP fragments. Over one single link hop (it does not have to be a single physical link, it could also be a bundle of physical links as well), hereinafter referred to as the one hop case, the delay can not be affected but if MP fragmentation is used over several serial PPP links in a row, the delay is decreased by sending the MP fragments to the end router where MP fragmentation is used without reassembling the MP fragments to IP packets at each intermediate router. In the present invention, this is called MP pipelining. The invention concerns the situation where at least two subsequent PPP links are using MP fragmentation.
When MP fragments from several IP packets are transported in parallel, as in the present invention, it is impossible to reassemble them correctly if it is not possible to differentiate the MP fragments by employing different classes. This may be done by the MP Multi-Class Extension (MCE) protocol. The MCE allows a sender to fragment the packets of various priorities into multiple classes of fragments, and thereby allowing high-priority packets to be sent between fragments of lower priorities, as well as fragments belonging to different IP packets of same priority are allowed to exist mixed on a single link. MP multi-class extension bits 100 are located in the MP header as shown in FIG. 1. Otherwise, these bits are unused if MCE is not employed. An MP fragment may comprise a long header or a short header. The long header uses 4 bits for multi-class extension and in the short header 2 bits are used. The multi-class extension to MP is further described in RFC 2686 that is further defined below.
In MP pipelining, the long low-priority IP packets are fragmented and MP MCE framed, and in the present invention they are referred to as MP MCE fragments. The high-priority IP packets may only be PPP framed, but if the PPP link is a bundle (several physical links), reordering might occur between the PPP packets. An alternative is thus to also MP MCE frame these packets, in addition to the PPP frame. However, these packets are only framed, not fragmented. In the present invention they are referred to as PPP frames but it should be noted that MP MCE may also be used and they may hence also be MP MCE frames.
Furthermore, FIG. 7a illustrates an egress interface without MP pipelining where MP MCE is used but it may also be the first interface in a pipeline. The respective IP classes (i.e. high 702 and low priority 704) are associated with an MP MCE class. The high priority IP packets are sent into an MP MCE/PPP framing unit and further to a scheduler 712. The low priority IP packets are sent into an MP MCE fragmenting and framer unit 708, where MP MCE fragments are created and the fragments are then sent into an MP MCE buffer 710. The scheduler 712 schedules the MP MCE fragments 728 in between the PPP frames 729 comprising the high priority data packets. FIG. 7b illustrates thus an ingress interface without pipelining where MP MCE is used. The PPP frames 729 and the MP MCE fragments 728 are demultiplexed in a demultiplexer 714 and the PPP frames 729 are further sent to a MP MCE/PPP deframer unit 716 while the MP MCE fragments are sent into a buffer 710 and then to a subsequent MP MCE defragmenting/deframer unit 718. This results in two separate queues of high priority and low priority data packets. Thus, these deframing and defragmenting procedures are performed subsequently to every hop.
U.S. Pat. No. 5,497,371 describes a packet transport system for mixed traffic in which a packet fragmentation protocol allows traffic of different classes to occupy a single physical link. Low priority packets are fragmentated while high priority packets are never fragmentated. In order to avoid potential fragment mis-ordering, packets are only allowed to be fragmentated on a trunk or a link, where the link acts like a first-in first-out buffer.
U.S. Pat. No. 6,072,772 shows a crossbar switch where fragmentation of packets with variable size into packets with a fixed size provides guarantees for deterministic bandwidth and delay.
U.S. Pat. No. 6,148,000 shows a switching apparatus for receiving and transmitting data units each segmented into a series of cells of data. The apparatus comprising a storage device for storing the series of cells received at each incoming port until the last cell of said series is received.
K. Sklower et. Al., “The PPP Multilink Protocol (MP)”, RFC 1900 proposes a method for splitting, recombining, and sequencing datagrams across multiple logical data links.
C. Bormann, “The Multi-Class Extension to Multi-Link PPP”, RFC 2686 proposes a fragment-oriented solution for the real-time encapsulation format part of the architecture. This document is regarded as the closest prior art.
Thus, the objective problem of the present invention is to enhance performance for data packets when a link layer protocol adapted to fragment said data packets, e.g. the MP is used within a packet switched network.